Thiết lập bài toán Đồ thị phẳng

Bài toán này có thể được mô hình bằng đồ thị phân đôi đầy đủ K 3 , 3 {\displaystyle K_{3,3}} . Câu hỏi ban đầu có thể diễn đạt như sau: Có thể vẽ K 3 , 3 {\displaystyle K_{3,3}} trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau (ở một điểm không phải là điểm mút của các cạnh)?

Tổng quát:

  • Có thể vẽ một đồ thị trên một mặt phẳng không? Có các cạnh nào cắt nhau không?
  • Khi nào có thể tìm được ít nhất một cách biểu diễn đồ thị không có cạnh cắt nhau?